/**
 *  Insertion Sort - Recursive Implementation
 *
 */

class InsertionSort2<E extends Comparable<E>> {

    public void sort(E[] arr, int p) {
        int N = arr.length;
        
        if (N < 2 || p == 0) {
            return;
        }

        sort(arr, p - 1);

        insertion(arr, p);
    }

    private void insertion(E[] arr, int p) {
        for (int i = p; i > 0; i--) {
            if (arr[i].compareTo(arr[i - 1]) < 0) {
                swap(arr, i, i - 1);
            }
        }
    }

    private void swap(E[] arr, int i, int j) {
        E tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
